package com.ai.zuochengyun.phase01.class03;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 是否是完全二叉树
 */
public class Code18_IsCompleteBinaryTree {

    public static void main(String[] args) {
        BinaryTreeNode head = new BinaryTreeNode(1);
        head.left = new BinaryTreeNode(2);
        head.right = new BinaryTreeNode(3);
        head.left.left = new BinaryTreeNode(4);
        head.left.right = new BinaryTreeNode(8);
        head.right.left = new BinaryTreeNode(5);
        head.right.right = new BinaryTreeNode(6);

        Code14_PrintBinaryTree.printTree(head);
        System.out.println("");
        System.out.println(isCBT(head));
    }

    public static boolean isCBT(BinaryTreeNode head) {
        // 边界条件
        if (head == null) {
            return true;
        }

        // 按层遍历
        Queue<BinaryTreeNode> queue = new LinkedList<>();
        queue.add(head);
        // 是否遇到过左右两个孩子不双全的节点
        boolean leaf = false;
        BinaryTreeNode left = null, right = null;
        while (!queue.isEmpty()) {
            BinaryTreeNode cur = queue.poll();
            left = cur.left;
            right = cur.right;

            // 按层遍历，有左孩子就压入队列，有右孩子再压入队列
            if (left != null) {
                queue.add(left);
            }
            if (right != null) {
                queue.add(right);
            }

            // 如果有经过两个孩子不全，又发现了当前节点不是叶子节点
            if (leaf && (left != null || right != null)) {
                return false;
            }
            // 有右孩子，没有左孩子
            if (left == null && right != null) {
                return false;
            }

            // 左右孩子只要有一个为空，将标记置为true
            if (left == null || right == null) {
                leaf = true;
            }
        }
        return true;
    }
}
